The present invention generally relates to the field of fingerprinting and recognition of data.
There are many problems that may benefit from efficient fingerprinting and recognition of data including searching for an image or images over the Internet. The scope of tracking and filtering through images available on the Internet or in large repositories may be daunting. Some authors of digital images may wish to track their works or identify if any of their images have been copied illegally. These images may be distorted versions of the originals. There is a need to identify copied versions of images that may be descendants of the original copyrighted images without having to embed any copy protection data into said images.
There are two main techniques utilized for solving the problem of identifying illegal copies of copyrighted information in the prior art. The first involves utilizing an image database(s), and the second is involves utilizing digital watermarking techniques.
Image database techniques identifying and finding images can be simplified into two phases as described by G. Pass and R. Zabih in an article entitled, Comparing Images Using Joint Histograms, J. of Multimedia Systems, 1998. The first is the image summary where every image in the database is “summarized” with identifying features computed prior to retrieval. These features are used in the query process (summary comparison) when the user presents a query; a comparison measure is used to retrieve some number of the most similar images based on their feature match.
A variety of papers attempt to classify these two phases in image databases. Some of the same concepts are classified under differing terminology. Some authors identify these classifications based on “image identification” properties, and others define them as being “image query” properties. Two examples such papers include an article entitled “Metadata for Building the Multimedia Patch Quilt” by V. Kashyap, K. Shah, and A. Sheth, in Multimedia Database Systems: Issues and Research Directions 297 (Springer-Verlag 1996) and an article entitled “A Unified Approach to data Modeling and Retrieval for a Class of Image Database Application” by V. N. Gudivada, V. V Raghavan, and K. Vanapipat, in Multimedia Database Systems: Issues and Research Directions 36 (1996). In “Metadata for Building the Multimedia Patch Quilt,” information about images is broken into three categories: content dependent, content-descriptive, and content-independent. Content dependent features are those that depend on the content of the image, such as color. Content-descriptive features are those that may describe the scene, such as mountain, car, or face. Content-independent features are those that do not rely on the image scene but properties of the image, such as scale and image file format.
Images may be indexed or categorized based on visual features, text annotation, assigned subjects, or image types. A lot of overlap exists in the classification of images and image queries. In the article “A Unified Approach to data Modeling and Retrieval for a Class of Image Database Application,” queries are classified into five areas: retrieval by browsing, retrieval by objective attributes, retrieval by spatial constraints, retrieval by shape similarity, and retrieval by semantic attributes. Retrieval by browsing (RBR) is an example of a thumbnail search by a user, looking for a match. Retrieval by objective attributes (ROA) attempts to retrieve images based on matching the attribute values. Retrieval by spatial constraints (RSC) considers the spatial relationship of objects within an image, such as overlap, adjacency, multiples, or groups of objects. Retrieval by shape similarity (RSS) matches images based on similar shapes. Retrieval by semantic attributes (RSA) is based on the user's perception and understanding about the image.
Digital watermarks techniques may have several desirable advantages over image database techniques of identifying images. Many digital watermarks are invariant to scale, changes in color, and image format. A digital watermark is preferably integrated with the image content so it cannot be removed easily without severely degrading the image. Watermarks may provide information embedded within the image content that may relate to the owner, license, or tracking of an image. This embedded information may be a code that may later be used to identify the image. Instead of searching for image properties, contents, or similarity measures, one can simply search for the code. The result of finding a matching code is the exact image containing that code. If multiple images contain the same code (author information), then the set of images containing that code may be returned. In image database terms, a query for an image containing an embedded watermark should yield an exact image match as opposed to “similar” images. Using an embedded code may free system resources from storing and processing image metadata (color, scale, content, objects, etc.).
A central task to multimedia information systems is the management of images (storage and retrieval). Research in the area of image databases has focused on retrieval based on objects within images and based in matching algorithms for image similarities or in annotation. Such methods provide a means to reduce the searchable universe in locating the right image.
Image database techniques in the prior art have many significant limitations. A variety of tools use combinations of these classifications in building queries and searching for images. Techniques such as content-based retrieval, or query by example are typically based on color, image content (objects), spatial relationships, and annotation of image objects. Some so called content-based queries still rely on associated text to initiate the query process.
As image database systems evolve, the queries must be developed to cope with human perception where the similarity of two items is measured by the end-user. The basic approaches to image querying has been referred to as query by content, query by example, and similarity retrieval. The common end result in with any of these approaches is the retrieval images that although similar to the target image, are not the exact image. The pseudo-manual classification employed by many image database query techniques is time-consuming and potentially error-prone. Collecting text from web pages and file names may incorrectly identify and index images.
Color histograms are often used to compare images. However, color histograms lack spatial information, so images with very different appearances can have similar histograms. Colors may also change without changing the content, scene, or objects in the image (e.g. convert to gray-scale).
Various image database approaches assume that all images are scaled to contain the same number of pixels (are of the same dimensions), or only a small variation is present in the size, position, and orientation of the objects in images. Several factors may make such restrictions difficult in image databases. The query image is typically very different from the target image, so the retrieval method must allow for some distortions. If the query is scanned, it may suffer artifacts such as color shift, poor resolution, and dithering effects. In order to match such imperfect queries more effectively, the image database system must accommodate these distortions and yet distinguishes the target image from the rest of the database.
Since the input is only approximate, the approach taken by many image database systems is to present the user with a small set of the most promising target images as output, rather than with a single “correct” match.
Current digital watermarking techniques also have limitations. Watermarks provide means to identify images independent of image format, size, and color. Most of these techniques are sensitive to cropping and/or to affine distortions. However, watermarks may survive manipulations that cause image database techniques to fail to recognize the appropriate images. Digital watermarks further reduce the scope and provide a means of tracking for images. Watermarks may be used to locate a specific image or copies; however, watermarks are dependent on survivability of the embedded information and are vulnerable to attacks.
Image identification and recognition relies on the survivability of embedded features. These embed features may be vulnerable to distortions that make the watermarks unreadable. Disabling a watermark or embedded message is fairly easy and software is available that automates the image processing techniques required to make enough subtle changes to the image as to disable the watermark. When a watermark fails, the reading mechanism may not detect the existence of a watermark and the task of finding the illicit copies becomes daunting, especially so when the owner may have tens of thousands of digital images (this becomes a problem similar to image database queries).
What is needed is an image identification system that may find copies of images that have gone through modifications including drastic color shifts, cropping, resealing, resampling, or cropping. Preferably, this method will be capable of fingerprinting images wherein the number of points needed for recognition is small, and the recognition process is fast and reliable.